package com.ztom.top100;

/**
 * 岛屿数量
 * <p>
 * https://leetcode-cn.com/problems/number-of-islands/
 *
 * @author ZhangTao
 */
public class Code59NumIslands {

    /**
     * 感染
     *
     * @param grid
     * @return
     */
    public int numIslands1(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    infect(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void infect(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length
                || j < 0 || j >= grid[0].length
                || grid[i][j] != '1') {
            return;
        }
        // 感染了之后修改值
        grid[i][j] = '*';
        // 上下左右去感染
        infect(grid, i - 1, j);
        infect(grid, i + 1, j);
        infect(grid, i, j - 1);
        infect(grid, i, j + 1);
    }

    /**
     * 并查集
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        UnionFound unionFound = new UnionFound(grid);
        for (int j = 1; j < n; j++) {
            if (grid[0][j - 1] == '1' && grid[0][j] == '1') {
                unionFound.union(0, j - 1, 0, j);
            }
        }
        for (int i = 1; i < m; i++) {
            if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
                unionFound.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] == '1') {
                    // 左
                    if (grid[i][j - 1] == '1') {
                        unionFound.union(i, j, i, j - 1);
                    }
                    // 上
                    if (grid[i - 1][j] == '1') {
                        unionFound.union(i, j, i - 1, j);
                    }
                }
            }
        }

        return unionFound.sets();
    }

    class UnionFound {
        private int[] parent;
        private int[] help;
        private int[] size;
        private int sets;
        private int col;

        public UnionFound(char[][] grid) {
            col = grid[0].length;
            int row = grid.length;
            int len = row * col;
            parent = new int[len];
            help = new int[len];
            size = new int[len];
            sets = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '1') {
                        int index = index(i, j);
                        parent[index] = index;
                        size[index] = 1;
                        sets++;
                    }
                }
            }
        }

        private int index(int r, int c) {
            return r * col + c;
        }

        public int father(int i) {
            int hi = -1;
            while (i != parent[i]) {
                help[++hi] = i;
                i = parent[i];
            }
            while (hi >= 0) {
                parent[help[hi--]] = i;
            }
            return i;
        }

        public void union(int r1, int c1, int r2, int c2) {
            int fA = father(index(r1, c1));
            int fB = father(index(r2, c2));
            if (fA != fB) {
                if (size[fA] >= size[fB]) {
                    parent[fB] = fA;
                    size[fA] += size[fB];
                } else {
                    parent[fA] = fB;
                    size[fB] += size[fA];
                }
                sets--;
            }
        }

        public int sets() {
            return sets;
        }
    }
}
